// https://www.lintcode.com/problem/most-frequent-subtree-sum/description

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root
     * @return: all the values with the highest frequency in any order
     */
    int freq = 0;
    int traverse(TreeNode* node, map<int, int>& rec) {
        if (!node) {
            return 0;
        }
        int left = traverse(node->left, rec);
        int right = traverse(node->right, rec);
        int val = node->val + left + right;
        rec[val]++;
        if (rec[val] > freq) {
            freq = rec[val];
        }
        return val;
    }
    vector<int> findFrequentTreeSum(TreeNode * root) {
        map<int, int> rec;
        vector<int> res;
        traverse(root, rec);
        for (map<int, int>::iterator it = rec.begin(); it != rec.end(); ++it) {
            if (it->second == freq) {
                res.push_back(it->first);
            }
        }
        return res;
    }
};